package 动态规划.可dp可二分;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/9 13:39
 */
public class K蛋问题 {
    /*
      对应leetcode 鸡蛋下落问题
     */

    /**
     *
     * @param N 表示 楼层的 高度
     * @param k  表示剩余的鸡蛋数量
     * @return  f（N，k） 表示的就是 N 层高度，k 个鸡蛋，在最差情况下，的 需要丢鸡蛋测试的次数
     * 主要是 这个 最差情况的理解
     */
    public static int recursion(int N,int k){
        // 0 层 高度，规定的 鸡蛋是不会碎的 也不需要 丢鸡蛋 测试 ，直接返回次数 0
        if(N == 0)
            return 0;
        // k == 1只有一个鸡蛋的情况下，就需要从第一层 开始， 一层一层的 开始丢鸡蛋进行测试
        // 我们 要考虑的是最差情况，所以，最差是 在 当前楼层 N 层时，鸡蛋还没碎 ，所以，当 k == 1 直接返回 当前楼层 高度 N
        if(k == 1 || N == 1)
            // 如果这里 N == 1 这个basecase 设置的话 ，那么  下面的 枚举 可以从 i = 2 开始
            return N;
        int ans = Integer.MAX_VALUE;
        // 现在 主要的 下手点 ，是从 哪一层开始 丢鸡蛋 进行测试，显然不知道，那样的话只有， 从 第一层开始枚举了
        // 所以 枚举的 量  就找到了 // 在 N 层楼 ，k 鸡蛋的 情况，枚举 在那层 开始丢是 最优解
        for(int i = 2;i <=N;i++){
            /*
              从  i 层 开始丢的时候 两种 情况
              ① ： 碎了 的话，那么 就需要 让鸡蛋数 k - 1，然后降低楼层
              ②： 没碎的话，那么就需要 向上 继续枚举 ，因为当前鸡蛋并没碎 ，可以继续用
              因为 是 最差情况，所以，如果选择从第 i 层 开始丢测试的话，会 选择 ① ②
              情况的 一个  max 作为最差情况
             */
            ans = Math.min(ans,Math.max(recursion(i - 1,k - 1),recursion(N - i,k)) + 1);
        }
        return ans;
    }


    /*
        从上面的 代码可以 看出 是从 i = 2 枚举到 N
        有序，可以使用 二分 进行枚举
        下面的代码和上面的 唯一区别 就是 在 枚举 从 哪一层开始 进行 丢的 时候
        不是 遍历，而是使用 二分来 找 提高速度
     */
    public static int recursionBinary(int N,int k){
        if(N == 0)
            return 0;
        if(k == 1 || N ==  1)
            return N;
        int ans = Integer.MAX_VALUE;
        int left = 2;
        int right = N;
        while (left <= right ) {
            int mid = left + right >> 1;
            ans = Math.min(ans,Math.max(recursionBinary(mid - 1,k - 1),recursionBinary(N - mid,k)) + 1);
        }
        return ans;
    }


    public static void main(String[] args) {
        int recursion = recursion(6, 2);
        System.out.println(recursionBinary(6,2));
        System.out.println(recursion);
    }
}
